package leetcode.Hot100;

import leetcode.TreeNode;
import leetcode.TreeNodeUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，
 * 以便稍后在同一个或另一个计算机环境中重建。
 * <p>
 * 设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。
 * 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
 * <p>
 * 编码的字符串应尽可能紧凑。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/serialize-and-deserialize-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/19 0:36
 */
public class Codec1 {

    public static void main(String[] args) {
        Codec1 codec1 = new Codec1();
        TreeNode root = TreeNodeUtil.getBT(new Object[]{3,2,4,1});
        System.out.println(codec1.serialize(root));
        System.out.println(codec1.deserialize(codec1.serialize(root)));
    }

    // 先序遍历和中序遍历（后序遍历和中序遍历）能确定一棵二叉树，不过没用上二叉搜索树这个条件
    // 二叉树的中序比遍历是单调递增的，这点可以通过先序遍历或者后序遍历的结果 sorted 可得
    // Encodes a tree to a single string.
    //       4
    //   2        6
    // null 3   5  null
    // 先序遍历 4,2,3,6,5
    public String serialize(TreeNode root) {
        // root null
        if (root == null) return "";
        StringBuilder data = new StringBuilder();
        List<Integer> preorder = new ArrayList<>();
        preorderTraversalRec(root, preorder);
        for (Integer integer : preorder) data.append(integer).append(",");
        // 去掉末尾的 ","
        data.deleteCharAt(data.length() - 1);
        return data.toString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == "") return null;
        String[] split = data.split(",");
        List<Integer> preorder = new ArrayList<>();
        for (String num : split) {
            preorder.add(Integer.valueOf(num));
        }
        int[] preOrderA = preorder.stream().mapToInt(Integer::intValue).toArray();
        int[] inOrderA = Arrays.stream(preOrderA).sorted().toArray();
        return buildTree(preOrderA, inOrderA);
    }

    // 先序遍历
    private void preorderTraversalRec(TreeNode root, List<Integer> preorder) {
        if (root == null) return;
        preorder.add(root.val);
        preorderTraversalRec(root.left, preorder);
        preorderTraversalRec(root.right, preorder);
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreexa(preorder, inorder, Integer.MAX_VALUE + 1);
    }

    private int pre = 0;
    private int in = 0;
    // 这里借鉴了LeetCode的非官方题解
    // 也是 buildTree 的求解思路
    public TreeNode buildTreexa(int[] preorder, int[] inorder, long stop) {
        // 数组为空时返回null pre++一直在变化，初始为0，其最终值应等于preorder.length - 1, 二者相等说明为空数组
        if (pre == preorder.length) {
            return null;
        }
        // 中序遍历数组in位置节点等于该子树根节点值，说明此时已遍历到底部，返回null值（最左下角的元素，此时执行in++操作，同时返回当前节点null值
        if (inorder[in] == stop) {
            in++;
            return null;
        }
        // val值相当于将树中的所有节点 按中左右顺序对其进行遍历(先序遍历)
        int val = preorder[pre++];
        TreeNode root = new TreeNode(val);
        // 每个节点都获取其对应的左右子树值（包括null)
        root.left = buildTreexa(preorder, inorder, val);
        // 最右边（右下角）右子树上界为Integer.MAX_VALUE+1，其余右子树则不断更新上界，对应该子树根节点所在子树的公共祖先根节点值
        root.right = buildTreexa(preorder, inorder, stop);
        return root;
    }
}
